package com.ting.test.algorithms.递归和动态规划.范围尝试模型;

import java.util.Stack;

/**
 * 给定一个字符串str，返回这个字符串的最长回文子序列长度
 * 比如 ： str = “a12b3c43def2ghi1kpm”
 * 最长回文子序列是“1234321”或者“123c321”，返回长度7
 * <p>
 * 范围尝试模型 重点在于考虑 开头和结尾的状况
 */
public class 最长公共回文解法2 {

    public static void main(String[] args) {
        String str1 = "a12b3c456d";

        int length = maxLength(str1);
    }

    /**
     * @param str1
     * @return
     */
    private static int maxLength(String str1) {
        char[] arr1 = str1.toCharArray();

        // 这个方法其实就是求最长公共子序列的
        return process(arr1, 0, arr1.length);
    }

    private static int process(char[] arr, int L, int R) {
        if (L == R) {
            //如果L==R 则表示只有一个元素，肯定是有回文
            return 1;
        }
        if (L == R - 1) {
            //表示当前范围内有2个元素
            //如果这两个元素相等则回文长度为2，否则为0
            return arr[L] == arr[R] ? 2 : 0;
        }
        // 考虑几种情况
        //1. L肯定不在回文中，但R  肯定在回文中
        int p1 = process(arr, L + 1, R);
        //2. R肯定不在回文中，但L肯定在回文中
        int p2 = process(arr, L, R - 1);
        //3. R肯定不在回文中，L肯定不在回文中
        int p3 = process(arr, L + 1, R - 1);
        //3.  R肯定在回文中，L肯定在回文中 ，因为上面两种情况实际上已经包含了 R,L都不在的情况
        int p4 = arr[L] == arr[R] ? 2 + process(arr, L + 1, R - 1) : 0;
        return Math.max(Math.max(p1, p4), Math.max(p2, p3));
    }

    private static int dp(char[] arr) {
        int N = arr.length;
        int[][] dp = new int[N][N];

        // 注意 这里隐藏了一个条件  列下标不可能比行坐标小
        for (int i = 0; i < dp.length; i++) {
            dp[i][i] = 1;
        }

        for (int i = 1; i < dp.length; i++) {
            dp[i - 1][i] = arr[i - 1] == arr[i] ? 2 : 1;
        }


        for (int L = N - 3; L > 0; L--) {
            for (int R = L+2; R < N; R++) {// 注意 这里隐藏了一个条件  列下标不可能比行坐标小
                // 考虑几种情况
                //1. L肯定不在回文中，但R可能在回文中，也可能不在
                int p1 = dp[L + 1][R];
                //2. R肯定不在回文中，但L可能在回文中，也可能不在
                int p2 = dp[L][R - 1];
                int p4 = dp[L + 1][R - 1];
                //3.  R肯定在回文中，L肯定在回文中 ，因为上面两种情况实际上已经包含了 R,L都不在的情况
                int p3 = arr[L] == arr[R] ? 2 + dp[L + 1][R - 1] : 0;
                dp[L][R] = Math.max(Math.max(p1, p4), Math.max(p2, p3));
            }
        }

        return dp[0][N - 1];
    }

}
